# 双端动态
# class Solution(object):
#     def productExceptSelf(self, nums):
#         """
#         :type nums: List[int]
#         :rtype: List[int]
#         """
#         n = len(nums)
#         left = [1] * n
#         right = [1] * n
#         for i in range(1, n):
#             if i > 0:
#                 left[i] = left[i - 1] * nums[i - 1]
#                 right[-i - 1] = right[-i] * nums[-i]
#         output = [1] * n
#         for i in range(n):
#             output[i] = left[i] * right[i]
#         return output

# 单向动态
class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n = len(nums)
        answers = [1] * n
        for i in range(1, n):
            answers[i] = answers[i - 1] * nums[i - 1]
        R = 1
        for i in range(n - 2, -1, -1):
            R = R * nums[i + 1]
            answers[i] = answers[i] * R
        return answers



data = Solution()
nums = [1, 2, 3, 4]
print(data.productExceptSelf(nums))
